package com.example.algorithm.no0001.solution;

import com.example.algorithm.no0001.Solution;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description 两数之和-一遍hashMap
 * 时间复杂度：O(n)，
 * 我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。
 * 空间复杂度：O(n)，
 * 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。
 * @ClassName SumTwoNum
 * @Author Administrator
 * @Date 2020/5/16 12:48
 * @Version 1.0.0
 */
public class HashMapSolution1 implements Solution {

    /**
     * {2, 7, 11, 15}   9
     * @param nums      {2, 7, 11, 15}
     * @param target    9
     * @return
     */
    @Override
    public int[] twoSum(int[] nums, int target) {

        Map<Integer, Integer> map = new HashMap<>();

        for(int i=0; i< nums.length; i++){
            int remain = target - nums[i];
            // 如果 map 存在此差值，则返回
            if(map.containsKey(remain)){
                // 将该数组的值存入 map
                return new int[]{map.get(remain), i};
            }
            map.put(nums[i], i);
        }
        return null;
    }
}
